package leetcode.D100.T51;

import java.util.*;

class Solution {
    // 一刷
    /*private String[] basicString;
    public List<List<String>> solveNQueens(int n) {
        char[] temp = new char[n];
        Arrays.fill(temp, '.');
        basicString = new String[n];
        StringBuilder sb = new StringBuilder(String.copyValueOf(temp));
        for(int i=0; i<n; ++i) {
            sb.setCharAt(i, 'Q');
            basicString[i] = sb.toString();
            sb.setCharAt(i, '.');
        }
        List<List<String>> results = new LinkedList<>();
        Deque<String> dq = new LinkedList<>();
        int[] rows = new int[n + 1];
        dfs(results, rows, 1, dq, n);
        return results;
    }
    private void dfs(List<List<String>> result, int[] rows, int row, Deque<String> dq, int n) {
        if(dq.size() == n) {
            result.add(new LinkedList<>(dq));
            return;
        }
        for(int i=1; i<=n; ++i) {
            if(!check(rows, row, i)) {
                continue;
            }
            rows[i] = row;
            dq.addLast(basicString[i-1]);
            dfs(result, rows, row+1, dq, n);
            dq.removeLast();
            rows[i] = 0;
        }

    }
    private boolean check(int[] rows, int row, int col) {
        if(rows[col] > 0) {
            return false;
        }
        for(int i=1; i<rows.length; ++i) {
            if(rows[i] > 0 && (row-rows[i]) == Math.abs(col-i)) {
                return false;
            }
        }
        return true;
    }*/

    // 二刷
    private char[] basicChars;

    public List<List<String>> solveNQueens(int n) {
        basicChars = new char[n];
        Arrays.fill(basicChars, '.');
        int[] col2row = new int[n];
        Arrays.fill(col2row, -1);
        int[] path = new int[n];        // row2col
        List<List<String>> results = new ArrayList<>();
        dfs(results, col2row, path, 0);
        return results;
    }

    private void dfs(List<List<String>> results, int[] col2row, int[] path, int row) {
        if (row == path.length) {
            results.add(path2Result(path));
            return;
        }
        for(int col=0; col<path.length; ++col) {
            if (valide(row, col, col2row, path)) {
                col2row[col] = row;
                path[row] = col;
                dfs(results, col2row, path, row+1);
                col2row[col] = -1;
            }
        }
    }

    private boolean valide(int row, int col, int[] col2row, int[] row2col) {
        if (col2row[col] >= 0)
            return false;
        for(int i=0; i<row; i++) {
            int j = row2col[i];
            if ((row-i) == Math.abs(col-j))
                return false;
        }
        return true;
    }

    private List<String> path2Result(int[] row2col) {
        List<String> result = new ArrayList<>(row2col.length);
        for(int row=0; row<row2col.length; ++row) {
            int col = row2col[row];
            basicChars[col] = 'Q';
            result.add(new String(basicChars));
            basicChars[col] = '.';
        }
        return result;
    }
}